package org.algorithm.落雪.数组.三月.第四周;

import java.util.*;

/**
 * @author zhx
 * @version 1.0
 * @date 2022/03/24 8:32 PM
 * @description:  周四作业
 *
 *
 * url :  https://leetcode-cn.com/problems/n-queens/
 */
public class N皇后 {

    public static void main(String[] args) {
        System.out.println(solveNQueens(4));
    }


    public static List<List<String>> solveNQueens(int n){

        //创建三个哈希存储遍历过的列，两个方向的斜线
        Set<Integer> column = new HashSet<>();
        Set<Integer> diagonalS1 = new HashSet<>();
        Set<Integer> diagonalS2 = new HashSet<>();

        //创建list存储答案数组
        List<List<String>> res = new ArrayList<>();

        //创建path数组存储每行放置Q的位置
        int[] path = new int[n];

        dfs(0, n, res, path, column, diagonalS1, diagonalS2);

        return res;

    }

    public static void dfs(int row, int n, List<List<String>> res, int[] path,
                    Set<Integer> column, Set<Integer> diagonalS1, Set<Integer> diagonalS2) {
        //摆放完最后一行，输出一种棋盘摆放方案
        if (row == n) {
            List<String> list = convert(path, n);
            res.add(list);
            return;
        }

        //遍历第 row 行的 n 列(即 n 个格子)
        for (int i = 0; i < n; i++) {

            //判断第 i 个格子满足：1.与之前放置的皇后为不同列，且在不同两斜线
            if (!column.contains(i) && !diagonalS1.contains(row - i) && !diagonalS2.contains(row + i)) {

                //满足条件，则将此 i 加入path中，加入已遍历列colum和已遍历斜线两diag哈希
                path[row] = i;
                column.add(i);
                diagonalS1.add(row - i);
                diagonalS2.add(row + i);

                //已经找到该行的第i列符合要求，加入path中，然后递归到下一行
                dfs(row + 1, n, res, path, column, diagonalS1, diagonalS2);

                //当找到一种完全摆放方法，输出该方法之后return回来，然后回溯
                diagonalS2.remove(row + i);
                diagonalS1.remove(row - i);
                column.remove(i);
                path[row] = -1;
            }
        }
    }

    //将每一种棋盘摆放方案转换为字符串数组
    public static List<String> convert(int[] path, int n) {
        List<String> ans = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            char[] ch = new char[n];

            Arrays.fill(ch, '.');
            ch[path[i]] = 'Q';

            ans.add(new String(ch));
        }

        return ans;
    }

}
